package com.zklh.leetcode.other.problem46;

import java.util.LinkedList;
import java.util.List;

/**
 * @descrpiton 全排列功能实现
 * @author 坐看落花
 * @version 1.0
 * @date 2019/11/15
 */
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        if(nums.length == 0){
            return results;
        }else{
            List<Integer> basic = new LinkedList<>();
            basic.add(nums[0]);
            results.add(basic);
        }
        // 用于表示要增加到结果集的新的值
        int floor = 0;
        while(++floor < nums.length){
            int size = results.size();
            for (int i = 0; i < size; i++) {
                LinkedList<Integer> basic = (LinkedList<Integer>) results.get(i);
                for (int i1 = basic.size(); i1 >= 0; i1--) {
                    if(i1 == 0){
                        basic.addFirst(nums[floor]);
                    }else if (i1 == basic.size()){
                        LinkedList<Integer> newItem = new LinkedList<>(basic);
                        newItem.addLast(nums[floor]);
                        results.add(newItem);
                    }else{
                        LinkedList<Integer> newItem = new LinkedList<>(basic);
                        newItem.add(i1,nums[floor]);
                        results.add(newItem);
                    }

                }
            }
        }
        return results;
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        List<List<Integer>> results = solution.permute(new int[]{1,2,4,5});
        System.out.println(results);
    }
}

